简单排序

常用的排序算法分析：选择排序，冒泡排序，插入排序

选择排序

算法原理

首先遍历数组找到最小（大）元素，存放到数组的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕

void selectSort(int a[]) {
    int len = a.size();
    int min_index; //需要记录最小值和下标
    if(len <= 1)return;
    for(int i=0;i<len;++i){
        min_index=i;
        for(int j=i;j<len;++j){
            if(a[min_index]>a[j]){
                min_index=j;
            }
        }
        int temp=a[i];
        a[i]=a[min_index];　//交换
        a[min_index]=temp;      
    }
}

性质

最稳定的排序算法

最坏，最好和平均时间复杂度总是$O(N^2)$

冒泡排序

算法原理

顺序依次相邻元素比较，大的往后移(从小到大排序)，这样能保证一轮过后最大的数在最后面。再进行一轮比较得到第二大的数，依次类推。

N个数排序需要重复N-1次；

第K次排序时，证明已经有K个数排好序，不需要再排。则第K次需要的比较的次数为(N-1-K)次；

所以可以用双重循环语句，外层控制循环多少趟，内层控制每一趟的循环次数

void BubbleSort(int a[]){
    int len=a.size();
    if(len<=1)return; //数组为空或者只有一个数
    for(int i=0;i<len-1;i++){ //n个数需要　重复　（n-1）次
        for(int j=0;j<len-1-i;++j){　//每一次都需要　比较　（n-1-i）次
            if(a[j]>a[j+1])swap(a[j],a[j+1]);
        }
    }
}

改进：当数组已经排好序时，可以直接跳出循环得到结果。不需要再做比较

void BubbleSort(int a[]){
    int len=a.size();
    bool flag=true; //true表示乱序，
    if(len<=1)return; 
    for(int i=0;i<len-1 && flag;i++){ 
        flag=false;
        for(int j=0;j<len-1-i;++j){　//如果没有进入if语句说明数组已经排好序，下次直接跳出。
            if(a[j]>a[j+1]){
                swap(a[j],a[j+1]);
                flag=true; //有元素交换，则说明排序未完成。
            }
        }
    }
}

性质

时间复杂度

1. 最好：$O(N)$。在数组已经是正序的情况下，只需要遍历一遍就可以跳出循环。
2. 最坏：$O(N^2)$。在数组逆序的情况下。
3. 平均：$O(N^2)$。

稳定排序

插入排序

算法原理

对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入

void insertSort(int a[]) {
    int len = a.size();
    if(len<=1)return;
    for(int i=1;i<len-1;++i){
        int j=i-1;
        int key=a[i];
        while( j>=0 && key>a[j] ){
            a[j+1]=a[j];
            --j;
        }
        a[j+1]=key;
    }
}

性质

时间复杂度：

1. 最好：$O(N)$。已经排好序的数组。遍历一遍。
2. 最坏：$O(N^2)$。逆序
3. 平均：$O(N^2)$。

不稳定排序：

序列5 8 5 2 9，第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。

参考